import matplotlib.pyplot as plt
import matplotlib as mpl
import math
import sys
from collections import deque
#待完成树的图形化创建
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 用来正常显示中文标签
mpl.rcParams['axes.unicode_minus'] = False  # 用来正常显示负号
print(mpl.matplotlib_fname())
#定义文本框和箭头格式
decisionNode = dict(boxstyle="sawtooth", fc="0.8") #fc表示框填充色，0-1表示黑到白
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")
#each data is a dict
data=[]
label=[]
#store each attr has how many zhi
lei={}
def is_number(string: str):
    try:
        float(string)
        return True
    except ValueError:
        pass
    return False
def readdata():
    with open('data1.txt',encoding='utf-8') as file:
        i=0
        for line in file:
            tmp=line.strip().split(',')
            del tmp[0]
            if i==0:
                global label
                label=tmp.copy()
                i+=1
                global lei
                lei=dict((k,set()) for k in label)
            else:
                k=0
                d={}
                for j in tmp:
                    kk=label[k]
                    d[kk] = j
                    sum=lei[kk]
                    if not is_number(j):
                        sum.add(j)
                    lei[kk]=sum
                    k+=1
                data.append(d)
def createPlot():
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    createPlot.axl = plt.subplot(111, frameon=False)
    plotNode('JCJD', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode('YJD', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    # nodeTxt:节点文本， centerPt:子节点， parentPt:父节点， nodeType:节点样式
    createPlot.axl.annotate(nodeTxt, xy=parentPt,xycoords='axes fraction',
                            xytext=centerPt, textcoords='axes fraction',
                            va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
def test(test_data,link):
    '''
    :param test_data: test data
    :return: the correct rate
    '''
    total=0
    correct=0
    for i in test_data:
        #the begin tree node
        j=0
        test:dict=data[i]
        while (link[j].result is None) and (len(link[j].children)!=0):
            attr=link[j].judege
            zhi=test.get(attr)
            for k in link[j].children:
                if link[k].attr_value==zhi:
                    j=k
        if link[j].result==test.get('好瓜') or ((link[j].result is None) and( link[j].MAX_lei()==test.get('好瓜'))):
            correct+=1
        total+=1
    print('correct:'+str(correct)+'\ntotal:'+str(total)+'\nrate:'+str(correct/total))

    return correct/total

class Treenode:
    #the node number
    current_index=0
    def __init__(self,parent=None,children=None,result=None,attr_name=None,
                 attr_value=None,reset_attr=None,reset_data=None,index=None,judege=None):
        '''
        :param parent: the parent node
        :param children: the children node
        :param result: the judge result
        :param attr_name:the judge attr's name
        :param attr_value: the judge value ahead
        :param reset_attr:the reset attr should be judge
        :param reset_data:the reset data (index)
        '''
        self.parent=parent
        if children is None:
            self.children=[]
        else:
            self.children=children
        self.result=result
        self.judege=judege
        self.attr_name=attr_name
        self.attr_value=attr_value
        self.reset_attr=reset_attr
        self.reset_data:list=reset_data
        self.index=index

    def Ent(self):
        count={}
        sum=len(self.reset_data)
        for sample in self.reset_data:
            zhi=data[sample].get('好瓜')
            i=count.get(zhi,0)
            count[zhi]=i+1
        lei=count.values()
        ent=0
        for num in lei:
            ent-=(num/sum)*math.log2(num/sum)
        return ent
    def show(self):
        print('the index:',self.index,'\nthe parent:',self.parent,'\nthe children:',self.children,
              '\nthe up node''s attr:',self.attr_name,'\nthe attr_value:',self.attr_value,'\nthe reset data:',
              self.reset_data,'\nthe reset attr:',self.reset_attr,'\nthe judege_attr:',self.judege,'\nresult:',self.result)
        print("{1:=^50}".format('',"Treenode"+str(self.index)))
    def is_number(self, string:str):
        try:
            float(string)
            return True
        except ValueError:
            pass
        return False
    def Gain(self):
        '''
        find the max Ent decline ,and its sum
        :return:change:the latter ent
                attr:the chose attribute
                divide_point ,if is used,it is the current attr's divide point
        '''
        change=sys.maxsize
        attr=''
        divide_point=None
        for judge_attr in self.reset_attr:
            if judge_attr=='好瓜':
                break
            #diffrent attr value
            count={}
            total=len(self.reset_data)
            value = []#store the lianxuzhi data
            for index in self.reset_data:
                #get the value of attr
                zhi=data[index].get(judge_attr)

                if not self.is_number(zhi):
                    i=count.get(zhi,{})
                    num=i.get(zhi,0)
                    i[zhi]=num+1
                    lei=data[index].get('好瓜')
                    lei_num=i.get(lei,0)
                    i[lei]=lei_num+1
                    count[zhi]=i
                else:
                    #if the attr's value is num
                    value.append(float(zhi))
            #the deal with the current data
            if len(value)>0:
                value.sort()
                #print(value)
                min=sys.maxsize
                #deal with each apart point
                for i in range(len(value)-1):
                    point=(value[i]+value[i+1])/2
                    current={}
                    for index in self.reset_data:
                        zhi = data[index].get(judge_attr)
                        if float(zhi)<point:
                            i=current.get('<'+str(point),{})
                            num=i.get('num',0)
                            i['num']=num+1
                            lei=data[index].get('好瓜')
                            lei_num = i.get(lei, 0)
                            i[lei] = lei_num + 1
                            current['<'+str(point)]=i
                        else:
                            i = current.get('>'+str(point), {})
                            num = i.get('num', 0)
                            i['num'] = num + 1
                            lei = data[index].get('好瓜')
                            lei_num = i.get(lei, 0)
                            i[lei] = lei_num + 1
                            current['>'+str(point)] = i
                    #print(current)
                    ent=0
                    for diff in current.values():
                        t=list(diff.values())
                        sum=t[0]
                        del t[0]
                        tmp = 0
                        for j in t:
                            tmp-=(j/sum)*math.log2(j/sum)
                        ent+=sum/total*tmp
                        #print(t)
                        if min>ent:
                            min=ent
                            count=current


            #print(count)
            ent_after=0
            for diff in count.values():
                tmp=list(diff.values())
                #print(tmp)
                sum=tmp[0]
                del tmp[0]
                ent_tmp=0
                for i in tmp:
                    ent_tmp-=(i/sum)*math.log2(i/sum)
                ent_after+=ent_tmp*sum/total
            if ent_after<change:
                change=ent_after
                attr=judge_attr
            if self.is_current(attr):
                #print(count.keys())
                divide_point=float(list(count.keys())[0][1:])
        return change,attr,divide_point
    def Gini(self):
        change = sys.maxsize
        attr = ''
        divide_point = None
        for judge_attr in self.reset_attr:
            if judge_attr == '好瓜':
                break
            # diffrent attr value
            count = {}
            total = len(self.reset_data)
            value = []  # store the lianxuzhi data
            for index in self.reset_data:
                # get the value of attr
                zhi = data[index].get(judge_attr)

                if not self.is_number(zhi):
                    i = count.get(zhi, {})
                    num = i.get(zhi, 0)
                    i[zhi] = num + 1
                    lei = data[index].get('好瓜')
                    lei_num = i.get(lei, 0)
                    i[lei] = lei_num + 1
                    count[zhi] = i
                else:
                    # if the attr's value is num
                    value.append(float(zhi))
            # the deal with the current data
            if len(value) > 0:
                value.sort()
                # print(value)
                min = sys.maxsize
                # deal with each apart point
                for i in range(len(value) - 1):
                    point = (value[i] + value[i + 1]) / 2
                    current = {}
                    for index in self.reset_data:
                        zhi = data[index].get(judge_attr)
                        if float(zhi) < point:
                            i = current.get('<' + str(point), {})
                            num = i.get('num', 0)
                            i['num'] = num + 1
                            lei = data[index].get('好瓜')
                            lei_num = i.get(lei, 0)
                            i[lei] = lei_num + 1
                            current['<' + str(point)] = i
                        else:
                            i = current.get('>' + str(point), {})
                            num = i.get('num', 0)
                            i['num'] = num + 1
                            lei = data[index].get('好瓜')
                            lei_num = i.get(lei, 0)
                            i[lei] = lei_num + 1
                            current['>' + str(point)] = i
                    # print(current)
                    ent = 0
                    for diff in current.values():
                        t = list(diff.values())
                        sum = t[0]
                        del t[0]
                        tmp = 1
                        for j in t:
                            #use Gini xishu
                            tmp -= (j / sum) **2
                        ent += sum / total * tmp
                        # print(t)
                        if min > ent:
                            min = ent
                            count = current

            ent_after = 0
            for diff in count.values():
                tmp = list(diff.values())
                # print(tmp)
                sum = tmp[0]
                del tmp[0]
                ent_tmp = 1
                for i in tmp:
                    ent_tmp -= (i / sum) **2
                ent_after += ent_tmp * sum / total
            if ent_after <= change:
                change = ent_after
                attr = judge_attr
            if self.is_current(attr):
                # print(count.keys())
                divide_point = float(list(count.keys())[0][1:])
        return change, attr, divide_point
    def MAX_lei(self):
        '''
        :return: max lei
        '''
        count = {}
        for i in self.reset_data:
            zhi = data[i].get('好瓜')
            num = count.get(zhi, 0)
            count[zhi] = num + 1
        # max_lei=max(count)
        # print(max_lei,count)
        max_lei =max(count,key=count.get)
        return max_lei
    def is_current(self,attr):
        global data
        for i in data:
            shuxing=i.get(attr)

            if self.is_number(shuxing):
                return True
        return False
    #problem
    @classmethod
    def PrePrun(cls,test_data:list,link=None,reset_data=None,reset_attr=None):
        '''
        :return:
        '''
        if link is None:
            link=[]
            top=Treenode(reset_data=reset_data,reset_attr=reset_attr,index=0)
            link.append(top)
        result=link.copy()
        pre=test(test_data=test_data,link=link)
        while True:
            result_tree=result.copy()
            mark=0
            for i in result_tree:
                if len(i.children)==0 and i.result is None:
                    pre_index=cls.current_index
                    unfold:deque=i.creat_tree()
                    latter=test(test_data=test_data,link=result_tree+list(unfold))
                    if latter>pre:
                        result.extend(unfold)
                        pre=latter
                    else:
                        cls.current_index=pre_index
                        i.children=[]
                        i.judege=None
                        i.result=i.MAX_lei()
                    mark=1
            if mark==0:
                break
        return result
    @classmethod
    def tree_show(cls,tree:list):
        for i in tree:
            if isinstance(i,Treenode):
                i.show()
    @classmethod
    def LatPrun(cls,test_data:list,link:list,):
        pre=test(test_data,link)
        for i in link:
            def Yezi(i):
                if i.result is None:
                    for j in i.children:
                        if link[j].result is None:
                            return False
                    return True
                else:
                    return False
            if Yezi(i):
                i.result=i.MAX_lei()
                latter=test(test_data,link)
                if latter>pre:
                    for j in i.children:
                        link[j]=None
                    i.children=[]
                else:
                    i.result=None
    def creat_tree(self):
        '''
        :return: the tree
        '''
        node = deque()
        change,change_attr,divide_point=self.Gini()
        #urrent node is the same lei
        if self.Ent()==0 and self.result==None:
            self.result=data[self.reset_data[0]].get('好瓜')
            # self.show()
        elif len(self.reset_data)==0:
            pass
            # self.show()
        #if the attr cannot judge the node,or the rest attr is empty
        elif change==self.Ent() or len(self.reset_attr)==0:
            count={}
            for i in self.reset_data:
                zhi=data[i].get('好瓜')
                num=count.get(zhi,0)
                count[zhi]=num+1
            max_lei=max(zip(count.values(),count.keys()))
            self.result=max_lei[1]
            # self.show()
        #can divide the node
        else:
            if not self.is_current(change_attr):
                self.judege=change_attr
            else:
                self.judege=change_attr+':divide_point:'+str(divide_point)
            count={}
            t=lei[change_attr]
            count=dict((k,[])for k in t)

            for i in self.reset_data:
                zhi=data[i].get(change_attr)
                if self.is_current(change_attr):
                    if float(zhi)<divide_point:
                        zhi='<'
                    else:
                        zhi='>'
                j=count.get(zhi,[])
                j.append(i)
                count[zhi]=j
            self.children=[i+self.current_index+1 for i in range(len(count.values()))]
            # self.show()

            for key in count.keys():
                Treenode.current_index+=1
                reset_data=count.get(key)
                reset_attr = self.reset_attr.copy()
                reset_attr.remove(change_attr)
                if len(reset_data)==0:
                    new=Treenode(parent=self.index,result=self.MAX_lei(),attr_name=change_attr,index=Treenode.current_index,
                         attr_value=key,reset_data=reset_data,reset_attr=reset_attr,children=[])
                    node.append(new)
                else:
                    new=Treenode(parent=self.index, attr_name=change_attr,index=Treenode.current_index,
                         attr_value=key, reset_data=reset_data, reset_attr=reset_attr,children=[])
                    node.append(new)
        return node
        #the attr is a current bianlian


readdata()
#print(label,data)
node=Treenode(reset_data=[0,1,2,5,6,9,13,14,15,16],reset_attr=label,index=0)
test_data=[3,4,7,8,10,11,12]
new=node.creat_tree()
tree=[node]
tree.extend(new)
while(len(new)!=0):
    new1=deque()
    for i in new:
        tmp=i.creat_tree()
        new1.extend(tmp)
    new=new1
    tree.extend(new)
test(test_data=test_data,link=tree)

Treenode.LatPrun(test_data,tree)
Treenode.tree_show(tree)
#prepunch
# pre_tree=Treenode.PrePrun(test_data=test_data,link=None,reset_data=[0,1,2,5,6,9,13,14,15,16],reset_attr=label)
# Treenode.tree_show(tree=pre_tree)




